package 力扣;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。

 实现 Solution class:

 Solution(int[] nums) 使用整数数组 nums 初始化对象
 int[] reset() 重设数组到它的初始状态并返回
 int[] shuffle() 返回数组随机打乱后的结果
  
 示例：

 输入
 ["Solution", "shuffle", "reset", "shuffle"]
 [[[1, 2, 3]], [], [], []]
 输出
 [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

 解释
 Solution solution = new Solution([1, 2, 3]);
 solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
 solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
 solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

 */

public class _384打乱数组 {

    private int[] array;  // 打乱数组
    private int[] origiinal; // 原数组
    private Random rand = new Random();
    public _384打乱数组(int[] nums) {
        array = nums;
        origiinal = nums.clone();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        array = origiinal;
        origiinal = origiinal.clone();
        return array;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        List<Integer> aux = getArrayCopy();
        for (int i = 0; i < array.length ; i++) {
            int nextInt = rand.nextInt(aux.size());
            array[i]= aux.get(nextInt); //随机
            aux.remove(nextInt);
        }
        return array;
    }

    private List<Integer> getArrayCopy() {
        List<Integer> ids = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            ids.add(array[i]);
        }
        return ids;
    }
}
